package 剑指offer;

/**
 * @description:
 * @author: ywk
 * @date: 2021-04-07
 */

import 抽象数据类型.ListNode;

/**
 * L0-L4,L1-L3,L2
 */
public class 重排链表 {
    public static void reorderList(ListNode head) {
        ListNode mid = head;
        ListNode first = head;
        ListNode cur = head;
        ListNode fast = head;
        ListNode curTmp = head;
        while (fast != null && fast.next != null) {
            if (fast.next.next == null) {
                mid = cur;
            }
            curTmp = cur;
            cur = cur.next;
            fast = fast.next.next;
            if (fast != null && fast.next == null) {
                mid = cur;
            }
        }
        mid = mid.next;
        if (mid == null) {
            return;
        }
        if (fast != null) {
            curTmp.next.next = null;
        } else {
            curTmp.next = null;
        }

        mid = reverseList(mid);
        ListNode pre = first;
        ListNode preNext = pre;
        ListNode back = mid;
        ListNode backNext;

        while (preNext != null && back != null) {
            preNext = pre.next;
            backNext = back.next;
            pre.next = back;
            back.next = preNext;
            back = backNext;
            pre = preNext;
        }
        if (back != null) {
            pre.next = back;
        }
    }

    public static ListNode reverseList(ListNode node) {
        ListNode pre = null;
        ListNode cur = node;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

   static ListNode reverseListRe(ListNode head) {
        if (head.next == null) return head;
        ListNode last = reverseListRe(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    public static void main(String[] args) {
        ListNode node = ListNode.buildNode(new int[]{1, 2, 3});
//        reorderList(node);

        ListNode.printListNode(reverseListRe(node));
    }

}
